Sorting অ্যালগরিদম: Bubble Sort, Merge Sort, Quick Sort

Sorting অ্যালগরিদম হল ডেটা বা উপাদানগুলিকে একটি নির্দিষ্ট ক্রম (যেমন, ছোট থেকে বড় বা বড় থেকে ছোট) অনুযায়ী সাজানোর প্রক্রিয়া। বিভিন্ন ধরনের সাজানোর অ্যালগরিদম রয়েছে, যার মধ্যে Bubble Sort, Merge Sort, এবং Quick Sort বেশ জনপ্রিয়। নিচে এই তিনটি সাজানোর অ্যালগরিদমের বিস্তারিত আলোচনা করা হলো।

1. Bubble Sort

Bubble Sort একটি সহজ এবং মৌলিক সাজানোর অ্যালগরিদম, যা সমান্তরালভাবে তালিকার মধ্যে পার্শ্ববর্তী উপাদানগুলোকে তুলনা করে এবং তাদের স্থান পরিবর্তন করে।

বৈশিষ্ট্য:

• সাদৃশ্য: সহজে বোঝা এবং বাস্তবায়ন করা যায়।
• টাইম কমপ্লেক্সিটি: গড় এবং সবচেয়ে খারাপ সময় O(n²), যেখানে n হলো উপাদানের সংখ্যা।
• স্পেস কমপ্লেক্সিটি: O(1) (ইন-প্লেস অ্যালগরিদম)।

উদাহরণ (C++):

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]); // স্থান পরিবর্তন
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    
    std::cout << "Sorted array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    return 0;
}

2. Merge Sort

Merge Sort একটি  (Divide and Conquer) ভিত্তিক সাজানোর অ্যালগরিদম। এটি একটি তালিকাকে মধ্য পয়েন্টে ভাগ করে দুইটি সাব-লিস্ট তৈরি করে এবং তারপর তাদের একত্রিত করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: O(n log n) (সব ক্ষেত্রে)।
• স্পেস কমপ্লেক্সিটি: O(n) (যেহেতু এটি অতিরিক্ত স্থান ব্যবহার করে)।

উদাহরণ (C++):

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    
    std::cout << "Sorted array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    return 0;
}

3. Quick Sort

Quick Sort একটি দ্রুত এবং কার্যকরী সাজানোর অ্যালগরিদম, যা একটি পিভট (pivot) নির্বাচন করে এবং তালিকার উপাদানগুলোকে সেই পিভটের সাথে তুলনা করে সাজিয়ে রাখে। এটি একটি বিভাজন এবং বিজয় (Divide and Conquer) ভিত্তিক অ্যালগরিদম।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: গড়ে O(n log n), কিন্তু সবচেয়ে খারাপ সময় O(n²) (যদি পিভট সঠিকভাবে নির্বাচিত না হয়)।
• স্পেস কমপ্লেক্সিটি: O(log n) (যেহেতু এটি ইন-প্লেস অ্যালগরিদম)।

উদাহরণ (C++):

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // পিভট নির্বাচন
    int i = (low - 1); // ছোট মানের জন্য সূচক

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]); // স্থান পরিবর্তন
        }
    }
    std::swap(arr[i + 1], arr[high]); // পিভটকে সঠিক অবস্থানে নিয়ে আসা
    return (i + 1);
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1); // ডিভাইড এবং বিজয়
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    
    std::cout << "Sorted array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    return 0;
}

সারাংশ

• Bubble Sort: সহজ, কিন্তু কম কার্যকরী (O(n²) টাইম কমপ্লেক্সিটি)। মূলত শিক্ষার উদ্দেশ্যে ব্যবহৃত হয়।
• Merge Sort: কার্যকরী এবং স্থিতিশীল (O(n log n) টাইম কমপ্লেক্সিটি)। বড় ডেটাসেটের জন্য উপযোগী।
• Quick Sort: দ্রুত এবং কার্যকরী, তবে পিভট নির্বাচনের উপর ভিত্তি করে টাইম কমপ্লেক্সিটি পরিবর্তিত হতে পারে (গড় O(n log n), সবচেয়ে খারাপ O(n²))।

এই সাজানোর অ্যালগরিদমগুলো ডেটা প্রক্রিয়াকরণ এবং বিভিন্ন অ্যালগরিদম ডেভেলপমেন্টে অত্যন্ত গুরুত্বপূর্ণ। সঠিক অ্যালগরিদম নির্বাচন করা একটি সফল সফটওয়্যার প্রকল্পের জন্য অত্যাবশ্যক।